Lập trình Đống nhị phân

Đống nhị phân thường được biểu diễn bởi một mảng thay vì một cây nhị phân. Nút cha và nút con của mỗi nút được xác định thông qua một vài phép tính dựa trên chỉ số của mảng, do đó không cần dùng đến con trỏ. Cách biểu diễn này là một ví dụ của cấu trúc dữ liệu ẩn (cấu trúc dữ liệu sử dụng bộ nhớ đúng bằng lượng thông tin cần thiết để lưu trữ dữ liệu, cộng với một lượng nhỏ thông tin phụ).

Giả sử n là số khóa trong đống và i là một chỉ số. Nếu nút gốc có chỉ số 0, và chỉ số các nút là từ 0 đến n-1, thì nút thứ i có

  • chỉ số các nút con là 2i+1 và 2i+2
  • chỉ số nút cha là ⌊ ( i − 1 ) / 2 ⌋ {\displaystyle \lfloor (i-1)/2\rfloor }

Nếu nút gốc có chỉ số 1, và chỉ số các nút là từ 1 đến n, thì nút thứ i có

  • chỉ số các nút con là 2i và 2i+1
  • chỉ số nút cha là ⌊ i / 2 ⌋ {\displaystyle \lfloor i/2\rfloor }